 /**
 * @a https://leetcode.cn/problems/combination-sum-ii/solutions/2363941/40-zu-he-zong-he-iihui-su-qing-xi-tu-jie-7y8s/
 */
#include "../common.h"

class Solution {
private:
    vector<vector<int>> ret;
    vector<int> state;
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int start = 0;
        bk(target, start, candidates);
        return ret;
    }
    void bk(int target, int start, const vector<int>& choices){
        if(target == 0)
        {
            ret.push_back(state);
            return;   
        }
        for(int i = start; i < choices.size(); ++i){
            if(target - choices[i] < 0) break;
            if (i > start && choices[i] == choices[i - 1]) continue;
            
            state.push_back(choices[i]);
            bk(target - choices[i], i + 1, choices);
            state.pop_back();
        }
    }
};